home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1997 / MacHack 1997.toast / Hacks / Hacks ’97 / Warrior’s Progress / source code / Source / Libraries / Trees / TreeNode.cp < prev    next >
Encoding:
Text File  |  1997-06-28  |  2.7 KB  |  177 lines  |  [TEXT/CWIE]
  1. // TreeNode.cp
  2.  
  3. #ifndef TreeNode_h
  4. #include "TreeNode.h"
  5. #endif
  6. #ifndef Tree_h
  7. #include "Tree.h"
  8. #endif
  9. #ifndef Swap_h
  10. #include "Swap.h"
  11. #endif
  12. #ifndef MinMax_h
  13. #include "MinMax.h"
  14. #endif
  15.  
  16. TreeNode::TreeNode()
  17.   : tree( 0 ),
  18.      parent( 0 ),
  19.      left( 0 ),
  20.      right( 0 )
  21.   {
  22.   }
  23.  
  24. TreeNode::~TreeNode()
  25.   {
  26.     Assert( left == 0 );
  27.     Assert( right == 0 );
  28.  
  29.     if ( tree != 0 )
  30.         tree->Remove( *this );
  31.     
  32.     Assert( tree == 0 );
  33.     Assert( parent == 0 );
  34.   }
  35.  
  36. TreeNode *TreeNode::NextNode() const
  37.   {
  38.     if ( right != 0 )
  39.       {
  40.         TreeNode *n( right );
  41.         while ( n->left != 0 )
  42.             n = n->left;
  43.         return n;
  44.       }
  45.  
  46.     const TreeNode *n( this );
  47.     while ( n->IsRightChild() )
  48.         n = n->parent;
  49.     
  50.     return n->parent;
  51.   }
  52.  
  53. TreeNode* TreeNode::PreviousNode() const
  54.   {
  55.     if ( left != 0 )
  56.       {
  57.         TreeNode *n( left );
  58.         while ( n->right != 0 )
  59.             n = n->right;
  60.         return n;
  61.       }
  62.  
  63.     const TreeNode *n( this );
  64.     while ( n->IsLeftChild() )
  65.         n = n->parent;
  66.     
  67.     return n->parent;
  68.   }
  69.  
  70. TreeNode* TreeNode::SiblingNode() const
  71.   {
  72.     if ( IsRoot() )
  73.         return 0;
  74.     
  75.     if ( IsLeftChild() )
  76.         return parent->right;
  77.     
  78.     Assert( IsRightChild() );
  79.     return parent->left;
  80.   }
  81.  
  82. TreeNode*& TreeNode::LinkFromAbove()
  83.   {
  84.     Assert( Owned() );
  85.     
  86.     if ( IsRoot() )
  87.         return tree->root;
  88.     
  89.     if ( IsLeftChild() )
  90.         return parent->left;
  91.     
  92.     Assert( IsRightChild() )
  93.     return parent->right;
  94.   }
  95.     
  96. void TreeNode::SwapWith( TreeNode& n )
  97.   {
  98.     if ( Owned() )
  99.         LinkFromAbove() = &n;
  100.  
  101.     if ( n.Owned() )
  102.         n.LinkFromAbove() = this;
  103.     
  104.     Swap( tree, n.tree );
  105.     Swap( parent, n.parent );
  106.     Swap( left, n.left );
  107.     Swap( right, n.right );
  108.     
  109.     if ( left != 0 )
  110.         left->parent = this;
  111.     if ( right != 0 )
  112.         right->parent = this;
  113.     
  114.     if ( n.left != 0 )
  115.         n.left->parent = &n;
  116.     if ( n.right != 0 )
  117.         n.right->parent = &n;
  118.     
  119.   }
  120.  
  121. void TreeNode::RotateUp()
  122.   {
  123.     Assert( Owned() );
  124.     Assert( !IsRoot() );
  125.     
  126.     TreeNode& falling( *parent );
  127.     
  128.     falling.LinkFromAbove() = this;
  129.     parent = falling.parent;
  130.     falling.parent = this;
  131.     
  132.     if ( falling.left == this )
  133.       {
  134.         if ( right != 0 )
  135.             right->parent = &falling;
  136.         falling.left = right;
  137.         right = &falling;
  138.       }
  139.      else
  140.       {
  141.         Assert( falling.right == this );
  142.         if ( left != 0 )
  143.             left->parent = &falling;
  144.         falling.right = left;
  145.         left = &falling;
  146.       }
  147.   }
  148.  
  149. uint32 TreeNode::Depth() const
  150.   {
  151.     uint32 depth = 0;
  152.     for ( const TreeNode *n = parent; n != 0; n = n->parent )
  153.         depth++;
  154.     
  155.     return depth;
  156.   }
  157.  
  158. bool TreeNode::Valid() const
  159.   {
  160.     if ( !Owned() )
  161.         return parent == 0 && left == 0 && right == 0;
  162.     
  163.     if ( left != 0 && left->parent != this )
  164.         return false;
  165.     
  166.     if ( right != 0 && right->parent != this )
  167.         return false;
  168.     
  169.     if ( left != 0 && left == right )
  170.         return false;
  171.     
  172.     if ( IsRoot() )
  173.         return tree->root == this;
  174.     
  175.     return IsLeftChild() || IsRightChild();
  176.   }
  177.